package main

import (
	"fmt"
	"sort"
)

// 三数之和为0

// 避免重复，排序

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	res := [][]int{}

	// a+b+c = 0
	// 固定a，求b+c=0
	for aIdx := 0; aIdx < n; aIdx++ {
		// 枚举不同的a，避免重复
		if aIdx > 0 && nums[aIdx] == nums[aIdx-1] {
			continue
		}

		// 查找b+c=0
		cIdx := n - 1
		tategt := -1 * nums[aIdx]
		// 枚举b
		for bIdx := aIdx + 1; bIdx < n; bIdx++ {
			if bIdx > aIdx+1 && nums[bIdx] == nums[bIdx-1] {
				continue
			}
			for bIdx < cIdx && nums[bIdx]+nums[cIdx] > tategt {
				cIdx--
			}
			// 可能b c重合
			if bIdx == cIdx {
				break
			}
			if nums[bIdx]+nums[cIdx] == tategt {
				res = append(res, []int{nums[aIdx], nums[bIdx], nums[cIdx]})
			}
		}
	}
	return res
}

func main() {
	nums := []int{-1, 0, 1, 2, -1, -4}
	res := threeSum(nums)
	fmt.Println(res)
}
